#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

// 2503. 矩阵查询可获得的最大分数
class Solution1
{
private:
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};

public:
    vector<int> maxPoints(vector<vector<int>>& grid, vector<int>& queries) 
    {
        int k = queries.size(), id[k];
        iota(id, id + k, 0);
        sort(id, id + k, [&](int i, int j) { return queries[i] < queries[j]; });

        vector<int> ret(k);
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
        pq.emplace(grid[0][0], 0, 0);
        grid[0][0] = 0;
        int m = grid.size(), n = grid[0].size(), cnt = 0;
        for(int qi : id)
        {
            int q = queries[qi];
            while(!pq.empty() && get<0>(pq.top()) < q)
            {
                ++cnt;
                auto [_, i, j] = pq.top();
                pq.pop();
                for(int k = 0; k < 4; ++k)
                {
                    int x = i + dx[k], y = j + dy[k];
                    if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y])
                    {
                        pq.emplace(grid[x][y], x, y);
                        grid[x][y] = 0;
                    }
                }
            }
            ret[qi] = cnt;
        }

        return ret;
    }
};

// 2500. 删除每行中的最大值
class Solution2
{
public:
    int deleteGreatestValue(vector<vector<int>>& grid) 
    {
        int m = grid.size(), n = grid[0].size();
        for(int i = 0; i < m; ++i)
        {
            sort(grid[i].begin(), grid[i].end());
        }  

        int ret = 0;
        for(int j = 0; j < n; ++j)
        {
            int mx = 0;
            for(auto& row : grid)
            {
                mx = max(mx, row[j]);
            }
            ret += mx;
        }
        return ret;
    }
};

// 2493. 将节点分成尽可能多的组
class Solution2
{
public:
    int magnificentSets(int n, vector<vector<int>>& edges) 
    {
        vector<vector<int>> g(n);
        for(auto& e : edges)
        {
            int x = e[0] - 1, y = e[1] - 1;
            g[x].push_back(y);
            g[y].push_back(x);
        }    
        
        int time[n], clock = 0; // time 充当 vis 数组的作用（避免在 BFS 内部重复创建 vis 数组）
        memset(time, 0, sizeof time);
        auto bfs = [&](int start)
        {
            int depth = 0;
            time[start] = ++clock;
            vector<int> q = {start};
            while(!q.empty())
            {
                vector<int> nxt;
                for(int x : q)
                {
                    for(int y : g[x])
                    {
                        // 没有在同一次 BFS 中访问过
                        if(time[y] != clock)
                        {
                            time[y] = clock;
                            nxt.push_back(y);
                        }
                    }
                }
                q = move(nxt);
                ++depth;
            }
            return depth;
        };

        int color[n];
        memset(color, 0, sizeof color);
        vector<int> nodes;
        function<bool(int, int)> isBipartite = [&](int x, int c)
        {
            nodes.push_back(x);
            color[x] = c;
            for(int y : g[x])
            {
                if(color[y] == c || (color[y] == 0 && !isBipartite(y, -c))) return false;
            }
            return true;
        };

        int ret = 0;
        for(int i = 0; i < n; ++i)
        {
            // color[i] 不为零则说明同一个连通块已经访问过了
            if(color[i]) continue;
            nodes.clear();
            if(!isBipartite(i, 1)) return -1;
            int maxDepth = 0;
            for(int x : nodes)
            {
                maxDepth = max(maxDepth, bfs(x));
            }
            ret += maxDepth;
        }
        return ret;
    }
};

// LCR 009. 乘积小于 K 的子数组
class Solution3
{
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) 
    {
        if(k <= 1) return 0;

        int ret = 0, left = 0, x = 1;
        for(int right = 0; right < nums.size(); ++right)
        {
            x *= nums[right];
            while(x >= k)
            {
                x /= nums[left];
                ++left;
            }
            ret += right - left + 1;
        }
        return ret;
    }
};

